//给定一个 正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true ，否则返回 false 。 
//
// 进阶：不要 使用任何内置的库函数，如 sqrt 。 
//
// 
//
// 示例 1： 
//
// 
//输入：num = 16
//输出：true
// 
//
// 示例 2： 
//
// 
//输入：num = 14
//输出：false
// 
//
// 
//
// 提示： 
//
// 
// 1 <= num <= 2^31 - 1 
// 
// Related Topics 数学 二分查找 
// 👍 328 👎 0

package com.cute.leetcode.editor.cn;
public class ValidPerfectSquare {
    public static void main(String[] args) {
        new ValidPerfectSquare().new Solution().isPerfectSquare(808201);
    }
    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * 使用二分法判断一个数是否为完全平方数
     */
    class Solution {
        public boolean isPerfectSquare(int num) {
            int left = 1;
            int right = num/2;
            while (left < right){
                int mid = left + (right-left)/2;
                if (mid == num/mid) return true;
                else if (mid<num/mid) left = mid+1;//注意这里的判断条件，不要直接相乘，防止越界
                else right = mid-1;
            }
            return left*left == num;
        }

        /**
         * 数学的方法：完全平方数可以分解成奇数的和，所以可以让num于奇数主意做差，看看最后是否恰好为0
         */
        public boolean isPerfectSquare2(int num) {
            int i = 1;
            while (num>0){
                num -=i ;
                i += 2;
            }
            return num == 0;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}